/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-01
 * Time: 23:20
 */
public class Solution {
//     DP
//     dp[i], 表示凑成 i , 所需要的最少硬币个数
//     因为表示最小, 所以为 dp[ i-coins[j] ]...中的最小值
//     所以需要遍历 coins 数组, 找到能凑出结果的最小的那个
//     注意题目并没有说是递增的, 所以不能中途因为 value > i 就退出循环
    public int coinChange(int[] coins, int amount) {
        int length=coins.length;
        int[] dp=new int[amount+1];
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            // 注意这里 min 的初始值必须为(大于等于) amount+1
            // 用 [2] 3  即可知道
            int min=amount+1;
            // 所以需要遍历 coins 数组, 找到能凑出结果的最小的那个
            for(int j=0;j<length;j++){
                // 注意题目并没有说是递增的, 所以不能中途因为 value > i 就退出循环
                int value=coins[j];
                if(value<=i){
                    min=Math.min(min, dp[i-value]+1);
                }
            }
            dp[i]=min;
        }
        return dp[amount]>amount?-1:dp[amount];
    }
}
